package org.example.graph_theory;

import java.util.Arrays;
import java.util.LinkedList;

public class Find_if_there_is_a_path_in_the_graph {
    public static void main(String[] args) {
        //寻找图中是否存在路径

        //有一个具有 n 个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。
        //请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。
        //给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination 存在 有效路径 ，则返回 true，否则返回 false 。

        int n = 10;
//        int[][] edges = {{0,1},{1,2},{2,0}};
//        int[][] edges = {{0,1},{0,2},{3,5},{5,4},{4,3}};

        int[][] edges = {{0,7},{0,8},{6,1},{2,0},{0,4},{5,8},{4,7},{1,3},{3,5},{6,5}};

        int source = 7;
        int destination = 5;

        boolean b = validPath(n, edges, source, destination);
        System.out.println(b);

    }

    //并查集超时
    public static boolean validPath(int n, int[][] edges, int source, int destination) {
        int[] father = new int[n];
        int[] deep = new int[n];

        //初始化
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }

        //连接
        for (int i = 0; i < edges.length; i++) {
            int s = edges[i][0];
            int d = edges[i][1];
            int source_s = find(s,father);
            int source_d = find(d,father);
            if (source_s == source_d) continue;
            if (deep[source_s] > deep[source_d]){
                father[source_d] = source_s;
            } else if (deep[source_s] < deep[source_d]) {
                father[source_s] = source_d;
            }else {
                father[source_d] = source_s;
                deep[source_s]++;
            }

        }
        System.out.println(Arrays.toString(father));
        return find(source,father) == find(destination,father);
    }

    public static int find(int node,int[] father){
        if (father[node] == node) return node;
        return find(father[node],father);
    }

    //层序优先遍历超时
    public static boolean validPath2(int n, int[][] edges, int source, int destination) {
        if ( source == destination) return true;
        boolean[] visited = new boolean[edges.length];
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.add(source);
        while (!linkedList.isEmpty()){
            int size = linkedList.size();
            while(size>0){
                Integer node = linkedList.removeFirst();
                System.out.print(node+" ");
                for (int i = 0; i < edges.length; i++) {
                    if (visited[i]) continue;
                    if (edges[i][0] == node){
                        if (edges[i][1] == destination) return true;
                        visited[i] = true;
                        System.out.print(edges[i][1]+" ");
                        linkedList.add(edges[i][1]);
                    }
                    if (edges[i][1] == node){
                        if (edges[i][0] == destination) return true;
                        visited[i] = true;
                        System.out.print(edges[i][0]+" ");
                        linkedList.add(edges[i][0]);
                    }
                }
                System.out.println();
                size--;
            }
        }
        return false;
    }



}
